#include "SistemaPatrullas.h"
#include "Grafo.h"

SistemaPatrullas :: SistemaPatrullas(){
    this->graph = Grafo<char>(0);
    recorridos = vector< list<int> >(3);
}

SistemaPatrullas :: SistemaPatrullas( const char * archIN ){
    ifstream archivoIN(archIN);
    
    //entrada
    archivoIN >> cantEstaciones;
    archivoIN >> cantTuneles;
    archivoIN >> cantMoviles;
    
    graph = Grafo<char>(cantEstaciones);

    int nodoA, nodoB;
    for(int tunel = 1; tunel <= cantTuneles; tunel++){
        archivoIN >> nodoA;
        archivoIN >> nodoB;

        graph.agregarArco( nodoA , nodoB , 1 );
        graph.agregarArco( nodoB , nodoA , 1 );
    }

    estacionConMovil = vector<int>(cantMoviles);
    
    for(int movil = 0; movil < cantMoviles; movil++)
        archivoIN >> estacionConMovil[movil];
    
    
    archivoIN >> estacionEmergencia;
    
    recorridos = vector< list<int> >(3);
    
    archivoIN.close();
}
        
bool ordenar( list<int> i , list<int> j ){
    return i.size() < j.size();
}

bool SistemaPatrullas :: resolver(){

    vector<int> distancias;
    vector<int> distanciasMinimas(3,INF);
    vector<int> patrullas(3);
    
    /* Busco las 3 patrullas que van a participar de
     * la emergencia. Para esto aplico Dijkstra en la
     * estacion de emergencia y busco las 3 patrullas
     * mas cercanas.
     */
    
    graph.dijkstra( estacionEmergencia , distancias );
    
    for( unsigned i = 2 , j = 0 ; i >= 0 && j < 3 ; i-- , j++ ){
        distanciasMinimas[j] = distancias[estacionConMovil[i]];
        patrullas[j] = estacionConMovil[i];
    }
  
    
    for( unsigned i = 3 ; i < estacionConMovil.size() ; i++ ){
        
        if( distancias[estacionConMovil[i]] > 0 ){
            
            if( distancias[estacionConMovil[i]] < distanciasMinimas[0] ){
                
                distanciasMinimas[0] = distancias[estacionConMovil[i]];
                patrullas[0] = estacionConMovil[i];
                
            }else if ( distancias[estacionConMovil[i]] < distanciasMinimas[1] ){
                
                distanciasMinimas[1] = distancias[estacionConMovil[i]];
                patrullas[1] = estacionConMovil[i];
                
            }else if( distancias[estacionConMovil[i]] < distanciasMinimas[2] ){
                
                distanciasMinimas[2] = distancias[estacionConMovil[i]];
                patrullas[2] = estacionConMovil[i];
                
            }
        }
        
    }
    
        
    /* Elijo que nodo adyacente le queda mejor a cada patrulla.
     * mientras chequeo que no le haya asignado el mismo nodo a
     * 2 patrulas.
     */
    
    distanciasMinimas.clear();
    distanciasMinimas.resize( 3 , INF );
    
    vector< vector<int> > distanciasPatrullas( 3 );
    
    vector<int> ignorar,
                nodoAdjAsignado( 3 , -1 ),
                adyacentes;
                
    ignorar.push_back(estacionEmergencia);
    
      
    for( unsigned i = 0 ; i < distanciasPatrullas.size() ; i++ )
        graph.dijkstra( patrullas[i] , distanciasPatrullas[i] , 0 , ignorar );
    
    graph.getNodosAdyacentes( estacionEmergencia , adyacentes );
   
    for(unsigned i = 0 ; i < adyacentes.size() ; i++){
        
        for(unsigned j = 0 ; j < distanciasPatrullas.size() ; j++){
            
            if( distanciasPatrullas[j][ adyacentes[i] ] < distanciasMinimas[j] ){
                
                if( nodoAdjAsignado[0] != adyacentes[i] && 
                    nodoAdjAsignado[1] != adyacentes[i] &&
                    nodoAdjAsignado[2] != adyacentes[i] ){
                    
                    distanciasMinimas[j] = distanciasPatrullas[j][ adyacentes[i] ];
                    nodoAdjAsignado[j] = adyacentes[i];
                    
                }
                                
            }
                            
        }
        
    }
   
    /*  
    for( unsigned i = 0 ; i < nodoAdjAsignado.size() ; i++ )
        if( nodoAdjAsignado[i] == -1 )return false;*/
    
    for( unsigned i = 0 ; i < recorridos.size() ; i++ )
        graph.pathTo( patrullas[i] , nodoAdjAsignado[i] , recorridos[i] , ignorar );
           
    sort( recorridos.begin() , recorridos.end() , ordenar );
    
    list<int>::iterator it0 = recorridos[0].begin(),
                        it1 = recorridos[1].begin(),
                        it2 = recorridos[2].begin(),
                        aux;
                        
    //2 con 1
    for( unsigned i = 0 ; i < recorridos[1].size() ; i++ ){
        if( *(it1) == *(it2) ){
            aux = --it1;
            recorridos[1].insert( it1 , *(aux) );
        }
        it1++;
        it2++;
    }
    
    it0 = recorridos[0].begin();
    it2 = recorridos[2].begin();
    
    //2 con 0
    for( unsigned i = 0 ; i < recorridos[0].size() ; i++ ){
        if( *(it0) == *(it2) ){
            aux = --it0;
            recorridos[0].insert( it0 , *(aux) );
        }
        it0++;
        it2++;
    }
    
    it0 = recorridos[0].begin();
    it1 = recorridos[1].begin();
        
    //1 con 0
    for( unsigned i = 0 ; i < recorridos[0].size() ; i++ ){
        if( *(it0) == *(it1) ){
            aux = --it0;
            recorridos[0].insert( it0 , *(aux) );
        }
        it0++;
        it1++;
    }
    
    sort( recorridos.begin() , recorridos.end() , ordenar );
    
    while( recorridos[1].size() < recorridos[2].size() )
        recorridos[1].push_back( recorridos[1].back() );
    
    while( recorridos[0].size() < recorridos[2].size() )
        recorridos[0].push_back( recorridos[0].back() );
    
    for(unsigned i = 0 ; i < 3 ; i++)
        recorridos[i].push_back(estacionEmergencia);
    
    return true;
}

istream & operator >> ( istream & archivoIN , SistemaPatrullas & sistp ){
    
    //entrada
    archivoIN >> sistp.cantEstaciones;
    archivoIN >> sistp.cantTuneles;
    archivoIN >> sistp.cantMoviles;
    
    sistp.graph = Grafo<char>(sistp.cantEstaciones);

    int nodoA, nodoB;
    for(int tunel = 1; tunel <= sistp.cantTuneles; tunel++){
        archivoIN >> nodoA;
        archivoIN >> nodoB;

        sistp.graph.agregarArco( nodoA , nodoB , 1 );
        sistp.graph.agregarArco( nodoB , nodoA , 1 );
    }

    sistp.estacionConMovil = vector<int>(sistp.cantMoviles);
    
    for(int movil = 0; movil < sistp.cantMoviles; movil++)
        archivoIN >> sistp.estacionConMovil[movil];
    
    
    archivoIN >> sistp.estacionEmergencia;
    
    return archivoIN;
}

ostream & operator << ( ostream & out , const SistemaPatrullas & sistp ){
    list<int>::const_iterator it0 = sistp.recorridos[0].begin(),
                              it1 = sistp.recorridos[1].begin(),
                              it2 = sistp.recorridos[2].begin();
    
    out << sistp.recorridos[1].size() - 1 << endl;
                       
    for( unsigned i = 0 ; i < sistp.recorridos[0].size() ; i++ ){
        out << *it0++ << " ";
        out << *it1++ << " ";
        out << *it2++ << " ";
        out << endl;
    }
           
    return out;
}

//toString
string SistemaPatrullas :: toString(){
    string sistToString;
    
    ostringstream stream;

    stream << cantEstaciones;
    stream << cantTuneles;
    stream << cantMoviles;
    stream << estacionEmergencia;
      
    stream << graph.toString();

    for(int i = 0; i < estacionConMovil.size(); i++)
        stream << estacionConMovil[i];
            
//    for(int i = 0; i < recorridos.size(); i++)
  //      stream << recorridos[i];

    sistToString = stream.str();

    return sistToString;
}

//test
bool SistemaPatrullas :: test(){
     
     return true;
}
